package offer.day33;

import java.util.ArrayList;
import java.util.List;

public class No57First_FindNumbersWithSum {
    /*
     * 面试题57：和为s的数字
     * 题目一：和为s的两个数字
     * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得他们的和正好是s。
     * 如果有多对数字的和等于s，则输出任意一对即可。
     * 例如：输入数组{1，2，4，7，11，15}和数字15，由于4+11=15，因此输出4和11
     *
     *
     * 思路：
     * 方法一：时间复杂度O(n2)
     * 首先固定一个数字，然后和剩余的n-1个数字进行求和，判断其和是否等于s
     *
     * 方法二：时间复杂度O(n)
     * 首先选取两个指针：一个指向首部，一个指向尾部， 因为是一个递增排列的有序序列，所以可以
     * 然后对两个指针指向的数字进行求和，判断是否等于s：
     * 1>若等于s，则找到和为s的两个数字
     * 2>若小于s，则将第一个指针向后移动，使其指向更大的数字，然后再接着判断其和是否等于s
     * 3>若大于s，则将第二个指针向前移动，使其指向稍小的数字，然后再接着判断其和是否等于s，
     * 不断重复上诉过程直到第一个指针和第二个指针指向同一个数字为止
     *
     *
     *
     *
     * */
    public static void main(String[] args) {
        No57First_FindNumbersWithSum f = new No57First_FindNumbersWithSum();
        int[] array = {1,2,4,7,11,14};
        int sum = 15;
        List<int[]> twoNumbers = f.FindNumbersWithSum(array,sum);
        for(int[] ans:twoNumbers) {
            System.out.println("和为" + sum + "的两个数字分别是;" + ans[0] + " 和 " + ans[1]);
        }
    }

    private List<int[]> FindNumbersWithSum(int[] array, int sum) {
        if(array==null||array.length<0) return new ArrayList<>();

        List<int[]> result=new ArrayList<>();
        int start=0;
        int end=array.length-1;
        while(start<end){
            if(array[start]+array[end]==sum){
                int[] res=new int[2];
                res[0]=array[start];
                res[1]=array[end];
                result.add(res);
                start++;
            }else if(array[start]+array[end]<sum){
                start++;
            }else{
                end--;
            }
        }
        return result;
    }
}
